import bisect
import os
from openpyxl import load_workbook
from openpyxl.comments import Comment
from openpyxl.utils import get_column_letter

def find_min_rectangles(filename, sheet_name):
    wb = load_workbook(filename)
    ws = wb[sheet_name]

    rows = ws.max_row
    cols = ws.max_column

    cells = []
    for i in range(1, rows + 1):
        row = []
        for j in range(1, cols + 1):
            cell = ws.cell(row=i, column=j)
            border = cell.border
            left = border.left.style is not None
            right = border.right.style is not None
            top = border.top.style is not None
            bottom = border.bottom.style is not None
            row.append({'left': left, 'right': right, 'top': top, 'bottom': bottom})
        cells.append(row)

    for merged_range in ws.merged_cells.ranges:
        min_row, max_row, min_col, max_col = merged_range.min_row, merged_range.max_row, merged_range.min_col, merged_range.max_col
        left_top = ws.cell(row=min_row, column=min_col)
        border = left_top.border
        left = border.left.style is not None
        right = border.right.style is not None
        top = border.top.style is not None
        bottom = border.bottom.style is not None

        cells[min_row-1][min_col-1]['right'] = False
        cells[min_row-1][min_col-1]['bottom'] = False

        if left:
            for i in range(min_row, max_row + 1):
                cells[i-1][min_col-1]['left'] = True
        if right:
            for i in range(min_row, max_row + 1):
                cells[i-1][max_col-1]['right'] = True
        if top:
            for j in range(min_col, max_col + 1):
                cells[min_row-1][j-1]['top'] = True
        if bottom:
            for j in range(min_col, max_col + 1):
                cells[max_row-1][j-1]['bottom'] = True

    for i in range(rows):
        for j in range(cols):
            cell = cells[i][j]
            if cell['left'] and j > 0:
                cells[i][j-1]['right'] = True
            if cell['right'] and j < cols-1:
                cells[i][j+1]['left'] = True
            if cell['top'] and i > 0:
                cells[i-1][j]['bottom'] = True
            if cell['bottom'] and i < rows-1:
                cells[i+1][j]['top'] = True

    rows = len(cells)
    if rows == 0:
        return []
    cols = len(cells[0])

    col_left = [[0]*(rows+1) for _ in range(cols)]
    col_right = [[0]*(rows+1) for _ in range(cols)]
    for j in range(cols):
        for i in range(1, rows+1):
            cell = cells[i-1][j]
            col_left[j][i] = col_left[j][i-1] + (1 if cell['left'] else 0)
            col_right[j][i] = col_right[j][i-1] + (1 if cell['right'] else 0)

    row_top = [[0]*(cols+1) for _ in range(rows)]
    row_bottom = [[0]*(cols+1) for _ in range(rows)]
    for i in range(rows):
        for j in range(1, cols+1):
            cell = cells[i][j-1]
            row_top[i][j] = row_top[i][j-1] + (1 if cell['top'] else 0)
            row_bottom[i][j] = row_bottom[i][j-1] + (1 if cell['bottom'] else 0)

    sum_bottom = [[0]*(cols+1) for _ in range(rows+1)]
    sum_right = [[0]*(cols+1) for _ in range(rows+1)]
    for i in range(rows):
        for j in range(cols):
            sum_bottom[i+1][j+1] = sum_bottom[i+1][j] + sum_bottom[i][j+1] - sum_bottom[i][j] + (1 if cells[i][j]['bottom'] else 0)
            sum_right[i+1][j+1] = sum_right[i+1][j] + sum_right[i][j+1] - sum_right[i][j] + (1 if cells[i][j]['right'] else 0)

    rectangles = []

    for i1 in range(rows):
        for j1 in range(cols):
            for i2 in range(i1, rows):
                for j2 in range(j1, cols):
                    left_total = col_left[j1][i2+1] - col_left[j1][i1]
                    expected = i2 - i1 + 1
                    if left_total != expected:
                        continue
                    right_total = col_right[j2][i2+1] - col_right[j2][i1]
                    if right_total != expected:
                        continue
                    top_total = row_top[i1][j2+1] - row_top[i1][j1]
                    expected_col = j2 - j1 + 1
                    if top_total != expected_col:
                        continue
                    bottom_total = row_bottom[i2][j2+1] - row_bottom[i2][j1]
                    if bottom_total != expected_col:
                        continue
                    bottom_area = sum_bottom[i2][j2+1] - sum_bottom[i1][j2+1] - sum_bottom[i2][j1] + sum_bottom[i1][j1]
                    if bottom_area != 0:
                        continue
                    right_area = sum_right[i2+1][j2] - sum_right[i1][j2] - sum_right[i2+1][j1] + sum_right[i1][j1]
                    if right_area != 0:
                        continue
                    start_row = i1 + 1
                    start_col = j1 + 1
                    end_row = i2 + 1
                    end_col = j2 + 1
                    rectangles.append(((start_row, start_col), (end_row, end_col)))
    return rectangles

def find_max_rectangles(min_rectangles):
    # 将每个最小矩形转换为包含坐标和组成部分的结构
    rectangles = [{'coords': rect, 'components': [rect]} for rect in min_rectangles]

    def can_merge_horizontal(rect1, rect2):
        (s1_row, s1_col), (e1_row, e1_col) = rect1['coords']
        (s2_row, s2_col), (e2_row, e2_col) = rect2['coords']
        # 检查是否同一行范围且当前矩形的右列紧邻下一个矩形的左列
        return (s1_row == s2_row and e1_row == e2_row and e1_col + 1 == s2_col)

    def can_merge_vertical(rect1, rect2):
        (s1_row, s1_col), (e1_row, e1_col) = rect1['coords']
        (s2_row, s2_col), (e2_row, e2_col) = rect2['coords']
        # 检查是否同一列范围且当前矩形的下行紧邻下一个矩形的上行
        return (s1_col == s2_col and e1_col == e2_col and e1_row + 1 == s2_row)

    changed = True
    while changed:
        changed = False
        
        # 水平合并
        sorted_h = sorted(rectangles, key=lambda x: (x['coords'][0][0], x['coords'][0][1]))
        new_rects = []
        i = 0
        while i < len(sorted_h):
            current = sorted_h[i]
            j = i + 1
            while j < len(sorted_h):
                next_rect = sorted_h[j]
                if can_merge_horizontal(current, next_rect):
                    # 合并坐标
                    new_coords = (current['coords'][0], next_rect['coords'][1])
                    # 合并组成部分
                    new_components = current['components'] + next_rect['components']
                    current = {'coords': new_coords, 'components': new_components}
                    j += 1
                    changed = True
                else:
                    break
            new_rects.append(current)
            i = j
        rectangles = new_rects
        
        # 垂直合并
        sorted_v = sorted(rectangles, key=lambda x: (x['coords'][0][1], x['coords'][0][0]))
        new_rects = []
        i = 0
        while i < len(sorted_v):
            current = sorted_v[i]
            j = i + 1
            while j < len(sorted_v):
                next_rect = sorted_v[j]
                if can_merge_vertical(current, next_rect):
                    # 合并坐标
                    new_coords = (current['coords'][0], next_rect['coords'][1])
                    # 合并组成部分
                    new_components = current['components'] + next_rect['components']
                    current = {'coords': new_coords, 'components': new_components}
                    j += 1
                    changed = True
                else:
                    break
            new_rects.append(current)
            i = j
        rectangles = new_rects

    # 返回结果，包含坐标和组成部分
    return [{'coords': rect['coords'], 'components': rect['components']} for rect in rectangles]

def separateContentRegions(filename, sheet_name, min_rectangles):
    wb = load_workbook(filename)
    ws = wb[sheet_name]
    header_regions = []
    content_regions = []
    separate_lines = set()
    for min_rectangle in min_rectangles:
        (min_row, min_col), (max_row, max_col) = min_rectangle
        header_content = ""
        for row in ws.iter_rows(
            min_row=min_row,
            max_row=max_row,
            min_col=min_col,
            max_col=max_col,
            values_only=True 
        ):
            for cell_value in row:
                if cell_value:
                    header_content = header_content + str(cell_value)
        if header_content == "" or "签发日期" in header_content:
            content_regions.append({"pos": min_rectangle, "value": ""})
            for row in range(min_row, max_row+1):
                separate_lines.add(row)
        else:
            header_regions.append({"pos": min_rectangle, "value": header_content})
    # 第一轮分割过后，有些contents还是存在于headerregions里面，其实这些就是所谓的行标题
    row_titles = [item for item in header_regions if item['pos'][0][0] in separate_lines or item['pos'][1][0] in separate_lines]
    # 提取出来的列标题
    column_titles = [item for item in header_regions if item not in row_titles]
    return row_titles, column_titles, content_regions

def identify_contents(header_regions: list, content_regions: list):
    # 按照空白区域所占行，将header_regions 分成多个header_regions
    header_rows = [item['min_row'] for item in header_regions]
    content_rows = [item[0][0] for item in content_regions]
    # 将空白区域当作分割线
    separate_lines = list(set(content_rows))
    splitted_headers = split_list_with_reference(separate_lines, header_rows, header_regions)
    print(splitted_headers[0])
        

def split_list_with_reference(A, B, bvalues):
    """
    使用有序列表A分割有序列表B
    
    参数:
    A (list): 参考分割列表（无重复元素）
    B (list): 被分割列表（无重复元素，且与A无交集）
    
    返回:
    list: 分割后的子列表集合
    """
    # 预处理排序
    
    # 构建完整分割点（包含边界）
    split_points = [float('-inf')] + A + [float('inf')]
    result = []
    
    # 遍历所有分割区间
    for i in range(len(split_points)-1):
        left = split_points[i]
        right = split_points[i+1]
        
        # 计算元素边界索引
        start = bisect.bisect(B, left)
        end = bisect.bisect(B, right)

        # 提取区间元素
        segment = bvalues[start:end]
        if segment:
            result.append(segment)

    return result

from openpyxl.styles import PatternFill

def set_sheet_background(sheet, row_titles, color_hex):
    # 创建填充对象
    fill = PatternFill(start_color=color_hex, end_color=color_hex, fill_type="solid")
    
    # 遍历所有区域
    for region in row_titles:
        pos = region["pos"]
        (min_row, min_col), (max_row, max_col) = pos
        
        # 遍历区域内的每个单元格
        for row in range(min_row, max_row + 1):
            for col in range(min_col, max_col + 1):
                cell = sheet.cell(row=row, column=col)
                cell.fill = fill
    return sheet

def associate_titles_to_contents(content_regions, row_titles, column_titles):
    associated_contents = []
    for content in content_regions:
        content_pos = content['pos']
        content_value = content['value']
        (c_min_row, c_min_col), (c_max_row, c_max_col) = content_pos

        # 寻找关联的列标题（位于内容区域上方）
        related_row_titles = []
        for rt in column_titles:
            rt_pos = rt['pos']
            (rt_min_row, rt_min_col), (rt_max_row, rt_max_col) = rt_pos
            # 检查行标题是否在内容区域上方且列有包含关系
            vertical_overlap = rt_max_row < c_min_row
            horizontal_overlap = (rt_max_col >= c_max_col and rt_min_col <= c_max_col)
            if vertical_overlap and horizontal_overlap:
                related_row_titles.append(rt)

        # 按底部行号降序排列（最近的行标题优先）
        related_row_titles.sort(key=lambda x: x['pos'][1][0])

        # 寻找关联的行标题（位于内容区域左侧）
        related_col_titles = []
        for ct in row_titles:
            ct_pos = ct['pos']
            (ct_min_row, ct_min_col), (ct_max_row, ct_max_col) = ct_pos
            
            # 检查列标题是否在内容区域左侧且行有包含关系
            horizontal_overlap = ct_max_col < c_min_col
            vertical_overlap = (ct_max_row == c_max_row and ct_min_row == c_min_row)
            
            if horizontal_overlap and vertical_overlap:
                related_col_titles.append(ct)
        
        # 按右侧列号降序排列（最近的列标题优先）
        related_col_titles.sort(key=lambda x: x['pos'][1][1])
        
        # 提取标题值并过滤空值
        row_title_values = [rt['value'].strip() for rt in related_row_titles if rt['value'].strip()]
        col_title_values = [ct['value'].strip() for ct in related_col_titles if ct['value'].strip()]
        
        associated_contents.append({
            "pos": content_pos,
            "value": content_value,
            "列标题": row_title_values,
            "行标题": col_title_values
        })

    return associated_contents

def test():
    folder = "templates"
    for file in os.listdir(folder):
        if file.startswith("~") or not file.endswith(".xlsx"):
            continue
            
        file_name = os.path.join(folder, file)
        wb = load_workbook(file_name)
        sheet_names = wb.sheetnames
        sheet_name = sheet_names[2] if len(sheet_names) > 2 else sheet_names[0]
        
        # 提取最小矩形区域
        min_rectangles = find_min_rectangles(file_name, sheet_name)

        max_rects = find_max_rectangles(min_rectangles)
        # 输出每个合并后的矩形及其包含的最小矩形
        for rect in max_rects:
            print(f"合并后的矩形坐标: {rect['coords']}")
            print("包含的最小矩形:")
            for component in rect['components']:
                print(f"  {component}")
            mini_rectangles = rect['components']
            # 分割内容区域
            row_titles, column_titles, content_regions = separateContentRegions(file_name, sheet_name, mini_rectangles)
            # 关联标题信息
            # associated_data = associate_titles_to_contents(content_regions, row_titles, column_titles)
            # associated_data = find_associated_titles(row_titles, column_titles, content_regions)
            result = find_headers(row_titles, column_titles, content_regions)
            # 可视化标记（原代码逻辑）
            ws = wb[sheet_name]
            set_sheet_background(ws, row_titles, "BBFFFF")
            set_sheet_background(ws, column_titles, "98FB98")
            set_sheet_background(ws, content_regions, "FFFF00")
            # 打印示例结果
            print(f"\n文件 {file} 的分析结果：")
            for content in result:
                (min_row, min_col), (max_row, max_col) = content['pos']
                
                print(f"区域 {get_column_letter(min_col)}{min_row}:\
                        {get_column_letter(max_col)}{max_row} \
                      - 行标题: {content['left']}, 列标题: {content['top']}")
                ws.cell(row=min_row, column=min_col).comment = Comment(f"行标题: {content['left']}, 列标题: {content['top']}", "zhangsong")
        output_dir = "modified"
        os.makedirs(output_dir, exist_ok=True)
        wb.save(os.path.join(output_dir, file))
        return

def is_intersect(a_r1, a_r2, a_c1, a_c2, b_r1, b_r2, b_c1, b_c2):
    rows_overlap = a_r1 <= b_r2 and a_r2 >= b_r1
    cols_overlap = a_c1 <= b_c2 and a_c2 >= b_c1
    return rows_overlap and cols_overlap

def find_associated_titles(row_titles, col_titles, contents):
    rows_rects = []
    for r in row_titles:
        pos = r['pos']
        min_row, min_col = pos[0]
        max_row, max_col = pos[1]
        rows_rects.append((min_row, max_row, min_col, max_col))
    
    cols_rects = []
    for c in col_titles:
        pos = c['pos']
        min_row, min_col = pos[0]
        max_row, max_col = pos[1]
        cols_rects.append((min_row, max_row, min_col, max_col))
    
    content_non_empty_rects = []
    for c in contents:
        if c['value'] != '':
            pos = c['pos']
            min_row, min_col = pos[0]
            max_row, max_col = pos[1]
            content_non_empty_rects.append((min_row, max_row, min_col, max_col))
    
    result = {}
    for content in contents:
        c_pos = content['pos']
        c_min_row, c_min_col = c_pos[0]
        c_max_row, c_max_col = c_pos[1]
        # Process row titles
        candidates_row = []
        for r in row_titles:
            r_pos = r['pos']
            r_min_row, r_min_col = r_pos[0]
            r_max_row, r_max_col = r_pos[1]
            # 行标题的高度应该包含content所在区域，并且在内容区域的左边
            if (r_min_row <= c_min_row and r_max_row >= c_max_row) and (r_max_col < c_min_col):
                candidates_row.append(r)
        
        # 将这些候选的行标题从右到左排列
        candidates_row.sort(key=lambda x: x['pos'][1][1], reverse=True)
        matched_row = None
        for r in candidates_row:
            r_max_col_val = r['pos'][1][1]
            mid_c_min = r_max_col_val + 1
            mid_c_max = c_min_col - 1
            mid_r_min = c_min_row
            mid_r_max = c_max_row
            if mid_c_min > mid_c_max:
                matched_row = r
                break
            intersect = False
            for rect in rows_rects:
                r1, r2, c1, c2 = rect
                if is_intersect(mid_r_min, mid_r_max, mid_c_min, mid_c_max, r1, r2, c1, c2):
                    intersect = True
                    break
            if not intersect:
                for rect in cols_rects:
                    r1, r2, c1, c2 = rect
                    if is_intersect(mid_r_min, mid_r_max, mid_c_min, mid_c_max, r1, r2, c1, c2):
                        intersect = True
                        break
            if not intersect:
                for rect in content_non_empty_rects:
                    r1, r2, c1, c2 = rect
                    if is_intersect(mid_r_min, mid_r_max, mid_c_min, mid_c_max, r1, r2, c1, c2):
                        intersect = True
                        break
            if not intersect:
                matched_row = r
                break
        
        # Process column titles
        candidates_col = []
        for l in col_titles:
            l_pos = l['pos']
            l_min_row, l_min_col = l_pos[0]
            l_max_row, l_max_col = l_pos[1]
            if (l_min_col <= c_min_col and l_max_col >= c_max_col) and (l_max_row < c_min_row):
                candidates_col.append(l)
        
        candidates_col.sort(key=lambda x: x['pos'][1][0], reverse=True)
        matched_col = None
        for l in candidates_col:
            # 候选区域最大行
            l_max_row_val = l['pos'][1][0]
            # 候选区域相邻的下一行
            mid_r_min = l_max_row_val + 1
            # 候选区域的最小行的上一行
            mid_r_max = c_min_row - 1
            # 候选区域最小列
            mid_c_min = c_min_col
            # 候选区域最大列
            mid_c_max = c_max_col
            if mid_r_min > mid_r_max:
                matched_col = l
                break
            intersect = False
            for rect in rows_rects:
                r1, r2, c1, c2 = rect
                if is_intersect(mid_r_min, mid_r_max, mid_c_min, mid_c_max, r1, r2, c1, c2):
                    intersect = True
                    break
            if not intersect:
                for rect in cols_rects:
                    r1, r2, c1, c2 = rect
                    if is_intersect(mid_r_min, mid_r_max, mid_c_min, mid_c_max, r1, r2, c1, c2):
                        intersect = True
                        break
            if not intersect:
                for rect in content_non_empty_rects:
                    r1, r2, c1, c2 = rect
                    if is_intersect(mid_r_min, mid_r_max, mid_c_min, mid_c_max, r1, r2, c1, c2):
                        intersect = True
                        break
            if not intersect:
                matched_col = l
                break
        
        result[tuple(content['pos'])] = {
            'row_titles': [matched_row] if matched_row else [],
            'col_titles': [matched_col] if matched_col else []
        }
    
    return result

def find_headers(row_headers, column_headers, content_regions):
    # Prepare all regions with type
    all_regions = []
    for rh in row_headers:
        rh['type'] = 'row_header'
        all_regions.append(rh)
    for ch in column_headers:
        ch['type'] = 'column_header'
        all_regions.append(ch)
    for ct in content_regions:
        ct['type'] = 'content'
        all_regions.append(ct)
    
    # Assign left_ptr and top_ptr for each region
    for a in all_regions:
        a_min_row, a_min_col = a['pos'][0]
        a_max_row, a_max_col = a['pos'][1]
        
        # Find left_ptr
        left_candidates = []
        for b in all_regions:
            if b is a:
                continue
            b_min_row, b_min_col = b['pos'][0]
            b_max_row, b_max_col = b['pos'][1]
            if b_max_col < a_min_col:
                if b_min_row <= a_min_row and b_max_row >= a_max_row:
                    left_candidates.append(b)
        # Sort candidates by max_col descending
        left_candidates.sort(key=lambda x: x['pos'][1][1], reverse=True)
        a['left_ptr'] = left_candidates[0] if left_candidates else None
        
        # Find top_ptr
        top_candidates = []
        for b in all_regions:
            if b is a:
                continue
            b_min_row, b_min_col = b['pos'][0]
            b_max_row, b_max_col = b['pos'][1]
            if b_max_row < a_min_row:
                if b_min_col <= a_min_col and b_max_col >= a_max_col:
                    top_candidates.append(b)
        # Sort candidates by max_row descending
        top_candidates.sort(key=lambda x: x['pos'][1][0], reverse=True)
        a['top_ptr'] = top_candidates[0] if top_candidates else None
    
    # Process each content region to collect left and top headers
    result = []
    for content in content_regions:
        # Collect left headers (row_headers)
        left_list = []
        current = content.get('left_ptr')
        while current is not None:
            if current['type'] == 'row_header':
                left_list.append(current)
                current = current.get('left_ptr')
            else:
                break
        
        # Collect top headers (column_headers)
        top_list = []
        current = content.get('top_ptr')
        while current is not None:
            if current['type'] == 'column_header':
                top_list.append(current)
                current = current.get('top_ptr')
            else:
                break
        
        # Format the result without the 'type' and pointers
        formatted_left = [{'pos': item['pos'], 'value': item['value']} for item in left_list]
        formatted_top = [{'pos': item['pos'], 'value': item['value']} for item in top_list]
        
        result.append({
            'pos': content['pos'],
            'value': content['value'],
            'left': formatted_left,
            'top': formatted_top
        })
    
    return result

if __name__ == "__main__":
    test()